//
// Created by haozhenghui on 2020/12/2.
//
#include "sort/sort.h"
#include <string.h>
#include <stdlib.h>
#include <stdio.h>

int ctsort(int *data, int size, int k) {
    int *counts, *temp;
    int i, j;
    if ((counts = (int *) malloc(k * sizeof(int))) == NULL) {
        return -1;
    }
    if ((temp = (int *) malloc(size * sizeof(int))) == NULL) {
        free(counts);
        return -1;
    }
    memset(counts, 0, k * sizeof(int));
    memset(temp, 0, size * sizeof(int));
    for (j = 0; j < size; j++) {
//        printf("data[%d]:%d\n", j, data[j]);
        counts[data[j]] = counts[data[j]] + 1;
    }
    for (i = 1; i < k; i++) {
        counts[i] = counts[i] + counts[i - 1];
    }
    for (j = size - 1; j >= 0; j--) {
        temp[counts[data[j]] - 1] = data[j];
        counts[data[j]] = counts[data[j]] - 1;
    }
    memcpy(data, temp, size * sizeof(int));
    free(counts);
    free(temp);
    return 0;
}

